package my;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DPSolution {
	public static void main(String[] args) {

		DPSolution solution = new DPSolution();

		// 房屋盗贼，能偷的最多的钱
		int[] num = { 1, 5, 6, 8, 2, 4 };
		solution.rob(num);

		// 爬楼梯
		solution.climbStairs(10);

		// m*n矩阵，从左上顶点到右下角的全部路径总数
		solution.uniquePaths(3, 5);

		// 给定字典dict，将字符串S分割多个由字典里的字符组成
		String s = "catsanddog";
		// String s = "aaaaaaa";
		Set<String> dict = new HashSet<String>();
		dict.add("cat");
		dict.add("cats");
		dict.add("and");
		dict.add("sand");
		dict.add("dog");
		// dict.add("a");dict.add("aa");dict.add("aaaa");
		solution.wordBreak(s, dict);

		// 加入引入障碍物，计算m*n矩阵中的全部路径数

		int[][] obstacleGrid = { { 0, 0, 0, 1 }, { 0, 1, 0, 0 }, { 0, 0, 0, 0 } };
		solution.uniquePathsWithObstacles(obstacleGrid);

		// //找出三角形中和最小的路径
		int[] a1 = { 2 }, a2 = { 3, 4 }, a3 = { 6, 5, 7 }, a4 = { 4, 1, 8, 3 };
		List<Integer> l1 = new ArrayList<Integer>(), l2 = new ArrayList<Integer>(), l3 = new ArrayList<Integer>(), l4 = new ArrayList<Integer>();
		List<List<Integer>> triangle = new ArrayList<List<Integer>>();
		for (Integer a : a1)
			l1.add(a);
		triangle.add(l1);
		for (Integer a : a2)
			l2.add(a);
		triangle.add(l2);
		for (Integer a : a3)
			l3.add(a);
		triangle.add(l3);
		for (Integer a : a4)
			l4.add(a);
		triangle.add(l4);
		solution.minimumTotal(triangle);

		// 找出矩阵中最小和的路径
		int[][] grid = { { 1, 2, 3 }, { 2, 3, 4 }, { 1, 3, 5 } };
		solution.minPathSum(grid);

		// // 找出数组中最大和的子数组
		int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
		List<Integer> nums = new ArrayList<Integer>();
		for (Integer a : arr)
			nums.add(a);
		solution.maxSubArray(nums);

		// 找出数组中最大乘积的子数组
		int[] arr1 = { -6, 3, -2, 4, -3 };
		nums = new ArrayList<Integer>();
		for (Integer a : arr1)
			nums.add(a);
		solution.maxProduct(nums);

		// 给定一个数字字符串，得到所有的编码总数,A-Z表示1-26
		solution.numDecodings("123420912");

		// 给定字符串S和字典dict，计算所有的S由dict中词所能构成的组合
		solution.wordBreak2(s, dict);

		// 两个字符串是否为互扰字符串
		String s1 = "great";
		String s2 = "rgtea";
		solution.isScrambleII(s1, s2);

		// s3是否是有s1和s2通过交织可以得到
		s1 = "aabcc";
		s2 = "dbbca";
		String s3 = "aadbbcbcac";
		solution.isInterleave(s1, s2, s3);

		// 骑士拯救公主计算最小所需HP
		int[][] dungeon = { { -4, -5, 10 }, { -5, 3, -13 }, { 7, -6, -9 } };
		solution.calculateMinimumHP(dungeon);

		// 计算S中包含T上不同子序列的个数
		String S = "rabbbit";
		String T = "rabbit";
		solution.numDistinct(S, T);

		// 判断字符串S和P是否匹配，？表示任何单个元素，*表示任意序列字符串，包括空字符
		s = "";
		String p = "*";
		System.out.println("结果是：" + solution.isMatch(s, p));

		// 给定字符串，切割成多个回文字符串的最小切割数
		s = "abcbcabba";
		solution.minCut(s);

		// 给定序列1-n，计算有多少种二叉树形式
		solution.numTrees(2);

		// 给定序列1-n，求出所有可能的二叉树组合
		List<TreeNode> list = solution.generateTrees(2);
		TreeSolution tree = new TreeSolution();
		for (TreeNode l : list) {
			List<Integer> temp = tree.preorderTraversal(l, 0);
		}
		// 股票买卖，只能买入一次，卖出一次
		int[] price = { 56, 40, 65, 50, 75, 95, 65, 78, 55, 65, 48, 57, 75 };
		List<Integer> prices = new ArrayList<Integer>();
		for (Integer pri : price)
			prices.add(pri);
		System.out.println(solution.maxProfit(prices));

		// 可以进行多次股票买卖，但是不能持有两只股票，买入的时候必须保证手头股票已经卖掉
		System.out.println(solution.maxProfitII(prices));

		// 只能两次股票买卖，买入的时候必须保证手头股票已经卖掉
		System.out.println(solution.maxProfitIII(prices));

		// 可以进行k次买卖
		int k = 6;
		System.out.println(solution.maxProfitIV(k, price));

		// 两个字符串之间的距离
		String word1 = "adca";
		String word2 = "aadc";
		System.out.println(solution.minDistance(word1, word2));
	}

	// 两个字符串之间的距离
	public int minDistance(String word1, String word2) {
		int m = word1.length();
		int n = word2.length();
		if (m < 1 && n < 1)
			return 0;
		if (m < 1)
			return n;
		if (n < 1)
			return m;

		int[][] dp = new int[m + 1][n + 1];
		for (int i = 0; i <= m; i++) {
			dp[i][0] = i;
		}
		for (int j = 0; j <= n; j++) {
			dp[0][j] = j;
		}

		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					dp[i][j] = Math.min(dp[i - 1][j - 1],
							Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
				}
			}
		}
		return dp[m][n];
	}

	// 最多进行k次交易，最大利润
	public int maxProfitIV(int k, int[] prices) {
		if (prices.length < 2)
			return 0;
		if (k >= prices.length)
			return profit(prices);
		int[] local = new int[prices.length + 1];
		int[] global = new int[prices.length + 1];

		for (int i = 1; i < prices.length; i++) {
			int diff = prices[i] - prices[i - 1];
			for (int j = k; j > 0; j--) {
				local[j] = Math.max(local[j] + diff,
						global[j - 1] + Math.max(diff, 0));
				global[j] = Math.max(local[j], global[j]);
			}
		}
		return global[k];
	}

	private int profit(int[] prices) {
		int result = 0;
		for (int i = 0; i < prices.length; i++) {
			if (prices[i] - prices[i - 1] > 0) {
				result += prices[i] - prices[i - 1];
			}
		}
		return result;
	}

	// 只能两次股票买卖，买入的时候必须保证手头股票已经卖掉
	public int maxProfitIII(List<Integer> prices) {
		if (prices.size() < 2)
			return 0;
		int[] low = new int[prices.size()];
		int[] count = new int[prices.size()];
		low[0] = prices.get(0);
		for (int i = 1; i < prices.size(); i++) {
			low[i] = Math.min(low[i - 1], prices.get(i));
			count[i] = Math.max(count[i - 1], prices.get(i) - low[i]);
		}
		int[] high = new int[prices.size()];
		int[] reverse = new int[prices.size()];
		high[prices.size() - 1] = prices.get(prices.size() - 1);
		int result = 0;
		for (int i = prices.size() - 2; i >= 0; i--) {
			high[i] = Math.max(high[i + 1], prices.get(i));
			reverse[i] = Math.max(reverse[i + 1], high[i] - prices.get(i));
			result = Math.max(result, count[i] + reverse[i]);
		}

		return result;
	}

	// 可以进行多次股票买卖，但是不能持有两只股票，买入的时候必须保证手头股票已经卖掉
	public int maxProfitII(List<Integer> prices) {
		if (prices.size() < 2)
			return 0;
		int result = 0;
		int max = 0, min = 0;
		boolean isBuy = false, isSell = true;
		for (int i = 1; i < prices.size(); i++) {
			if (prices.get(i) > prices.get(i - 1) && !isBuy && isSell) {
				min = prices.get(i - 1);
				isSell = false;
				isBuy = true;
			}
			if (i < (prices.size() - 1) && prices.get(i) > prices.get(i + 1)
					&& isBuy && !isSell) {
				max = prices.get(i);
				isSell = true;
				isBuy = false;
				result += max - min;
			} else if (i == prices.size() - 1
					&& prices.get(i) > prices.get(i - 1) && isBuy && !isSell) {
				max = prices.get(i);
				result += max - min;
			}
		}
		return result;
	}
	
	// 股票买卖，只能买入一次，卖出一次
	public int maxProfit(List<Integer> prices) {
		int size = prices.size();
		if (size < 2)
			return 0;
		int[] min = new int[size];
		int[] max = new int[size];
		min[0] = prices.get(0);

		for (int i = 1; i < size; i++) {
			min[i] = Math.min(prices.get(i), min[i - 1]);
			max[i] = Math.max(prices.get(i) - min[i], max[i - 1]);
		}
		return max[size - 1];
	}

	// 给定序列1-n，求出所有可能的二叉树组合
	public List<TreeNode> generateTrees(int n) {
		return generateTrees(1, n);
	}

	private List<TreeNode> generateTrees(int left, int right) {
		List<TreeNode> list = new ArrayList<TreeNode>();
		if (left > right) {
			list.add(null);
			return list;
		}
		for (int i = left; i <= right; i++) {
			for (TreeNode l : generateTrees(left, i - 1)) {
				for (TreeNode r : generateTrees(i + 1, right)) {
					TreeNode root = new TreeNode(i);
					root.left = l;
					root.right = r;
					list.add(root);
				}
			}
		}
		return list;
	}

	// 给定1-n，计算有多少种二叉树形式
	public int numTrees(int n) {
		if (n <= 2)
			return n;
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= n; i++) {
			for (int j = 0; j < i; j++) {
				dp[i] += dp[j] * dp[i - j - 1];
			}
		}

		return dp[n];
	}

	// 给定字符串，切割成多个回文字符串的最小切割数
	public int minCut(String s) {
		if (s == null || s.length() < 2)
			return 0;
		// 动态数组
		int[][] dp = new int[s.length()][s.length()];
		// 存储最小切割数
		int[] count = new int[s.length() + 1];
		for (int i = s.length() - 1; i >= 0; i--) {
			count[i] = s.length() - i;
			for (int j = i; j < s.length(); j++) {
				if (s.charAt(i) == s.charAt(j)) {// 判断条件，
					// [i,j]为回文数的前提是[i+1，j-1]也是回文数，或者单个字符
					if (j - i < 2 || dp[i + 1][j - 1] == 1) {
						dp[i][j] = 1;
						// 状态转移方程，[i,j]是回文数，那么i~len与j+1~len之间的切割数取最小
						count[i] = Math.min(count[i], count[j + 1] + 1);
					}
				}
			}
		}
		return count[0] - 1;
	}

	// 判断字符串S和P是否匹配，？表示任何单个元素，*表示任意序列字符串，包括空字符
	public boolean isMatch(String s, String p) {
		if (s == null && p == null)
			return true;
		if (s == null || p == null)
			return false;
		if (s.equals("") && p.equals(""))
			return true;
		if (!s.equals("") && p.equals(""))
			return false;
		if (s.equals("")) {
			for (int i = 0; i < p.length(); i++)
				if (p.charAt(i) != '*')
					return false;
			return true;
		}

		int m = s.length();
		int n = p.length();
		boolean[][] dp = new boolean[m][n];
		dp[0][0] = s.charAt(0) == p.charAt(0) || p.charAt(0) == '?'
				|| p.charAt(0) == '*';// 起始值
		// 第一行
		for (int i = 1; i < m; i++) {
			if (s.charAt(i) == p.charAt(0) || p.charAt(0) == '?'
					|| p.charAt(0) == '*') {
				dp[i][0] = true;
			} else if (s.charAt(i) != p.charAt(0)) {
				dp[i][0] = false;
				break;
			}
		}

		// 第一列
		for (int j = 1; j < n; j++) {
			if (p.charAt(j - 1) == '*' || s.charAt(0) == p.charAt(j - 1)) {
				dp[0][j] = true;
			} else {
				dp[0][j] = false;
				break;
			}
		}

		// 剩余矩阵部分
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (p.charAt(j) == '*') {
					dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
				}
				if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?') {
					dp[i][j] = dp[i - 1][j - 1];
				}
			}
		}
		return dp[m - 1][n - 1];

	}

	// 计算S中包含T上的中不同的子序列个数
	public int numDistinct(String S, String T) {
		if (S == null || S.equals(""))
			return 0;
		if (T == null || T.equals(""))
			return 1;
		int m = S.length();
		int n = T.length();
		int[][] dp = new int[m + 1][n + 1];
		dp[0][0] = 1;
		// 如果T字符串为空串，那么它是任何字符串的子串，因此S中包含一个T子串
		for (int i = 1; i <= m; i++)
			dp[i][0] = 1;
		// 如果S是空串，那么它不包含任何子串
		for (int j = 1; j <= n; j++)
			dp[0][j] = 0;
		// 首先dp[i][j] = dp[i-1][j],表示S变长，至少包含S（i-1）
		// 如果S[i-1] == T [j-1],那么还需要加上dp[i-1][j-1].
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = dp[i - 1][j];
				if (S.charAt(i - 1) == T.charAt(j - 1))
					dp[i][j] += dp[i - 1][j - 1];
			}
		}
		return dp[m][n];
	}

	// 骑士拯救公主，自左向右，自上而下，不回头，骑士HP为正值，计算最小所需HP
	public int calculateMinimumHP(int[][] dungeon) {
		int m = dungeon.length;
		if (m == 0)
			return 1;
		int n = dungeon[0].length;
		if (n == 0)
			return 1;
		// 二维空间DP问题
		int[][] dp = new int[m][n];// dp[i][j]表示从(i,j)到目的地(m-1,n-1)需要的最小生命值
		// 初始化
		dp[m - 1][n - 1] = Math.max(0 - dungeon[m - 1][n - 1], 0);
		for (int i = m - 2; i >= 0; i--) {
			dp[i][n - 1] = Math.max(dp[i + 1][n - 1] - dungeon[i][n - 1], 0);
		}
		for (int i = n - 2; i >= 0; i--) {
			dp[m - 1][i] = Math.max(dp[m - 1][i + 1] - dungeon[m - 1][i], 0);
		}
		// 从下向上，从右向左填表
		// dp方程为 dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j] 再和0取最大
		for (int i = m - 2; i >= 0; i--) {
			for (int j = n - 2; j >= 0; j--) {
				dp[i][j] = Math.max(Math.min(dp[i][j + 1], dp[i + 1][j])
						- dungeon[i][j], 0);
			}
		}
		return dp[0][0] + 1;
	}

	// 给定3个字符串(s1,s2,s3)，看s3是否是有s1和s2通过交织可以得到
	public boolean isInterleave(String s1, String s2, String s3) {
		s1 = s1.trim();
		s2 = s2.trim();
		s3 = s3.trim();
		if (s1.length() + s2.length() != s3.length())
			return false;
		if (s1.equals(""))
			return s2.equals(s3);
		if (s2.equals(""))
			return s1.equals(s3);
		// 二维动态规划
		boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
		dp[0][0] = true;
		// 第一列，用s1与s3进行匹配
		for (int i = 1; i < s1.length(); i++) {
			char c1 = s1.charAt(i - 1);
			char c3 = s3.charAt(i - 1);
			if (c1 == c3)
				dp[i][0] = true;
			else
				break;
		}
		// 第一行，用s2与s3进行匹配
		for (int j = 1; j < s2.length(); j++) {
			char c2 = s2.charAt(j - 1);
			char c3 = s3.charAt(j - 1);
			if (c2 == c3)
				dp[0][j] = true;
			else
				break;
		}
		// 对矩阵剩余元素进行累积计算
		for (int i = 1; i <= s1.length(); i++) {
			for (int j = 1; j <= s2.length(); j++) {
				dp[i][j] = (dp[i][j - 1]
						&& (s1.charAt(i - 1) == s3.charAt(i + j - 1) // 判断能否从s1经过
						|| dp[i - 1][j]) && s2.charAt(j - 1) == s3.charAt(i + j
						- 1));// 判断能否从s2经过
			}
		}
		return dp[s1.length()][s2.length()];
	}

	// 判断两个字符串是否为互扰字符串，采用动态规划
	public boolean isScrambleII(String s1, String s2) {
		if (s1 == null || s2 == null)
			return true;
		if (s1.length() != s2.length())
			return false;
		if (s1.length() == 1)
			return s1.equals(s2);
		int len = s1.length();
		// 建立一个三维数组，第一维为s1，第二维为s2，第三维为长度
		boolean[][][] res = new boolean[len][len][len + 1];
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				// 将长度为1的字符串判断是否为互扰字符串
				res[i][j][1] = s1.charAt(i) == s2.charAt(j);
			}
		}
		// 对长度l进行2-len遍历
		for (int l = 2; l <= len; l++) {
			for (int i = 0; i < len - l + 1; i++) {
				for (int j = 0; j < len - l + 1; j++) {
					// 对1到l-1进行不断叠加
					for (int k = 1; k < l; k++) {
						res[i][j][l] |= res[i][j][k]
								&& res[i + k][j + k][l - k]
								|| res[i][j + l - k][k] && res[i + k][j][l - k];
					}
				}
			}
		}

		return res[0][0][len];
	}

	// 判断两个字符串是否为互扰字符串，采用递归
	public boolean isScramble(String s1, String s2) {
		if (s1 == null || s2 == null)
			return true;
		if (s1.length() != s2.length())
			return false;
		if (s1.length() == 1)
			return s1.equals(s2);
		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();
		Arrays.sort(c1);
		Arrays.sort(c2);
		for (int i = 0; i < s1.length(); i++) {
			if (c1[i] != c2[i]) {
				return false;
			}
		}
		String s11, s12, s21, s22;
		boolean result = false;
		for (int i = 1; i < s1.length() && !result; i++) {
			s11 = s1.substring(0, i);// s1的第一部分
			s12 = s1.substring(i, s1.length());// s1的第二部分
			s21 = s2.substring(s2.length() - i, s2.length());// s2的第一部分
			s22 = s2.substring(0, s2.length() - i);// s2的第二部分
			// 递归比较每一部分，首先保证长度一致
			result = isScramble(s12, s22) && isScramble(s11, s21);
			if (!result) {
				// 调换下次序，继续递归
				s21 = s2.substring(i, s2.length());
				s22 = s2.substring(0, i);
				result = isScramble(s11, s22) && isScramble(s12, s21);
			}
		}
		return result;
	}


	// 给定字符串S和字典dict，计算所有的S由dict中词所能构成的组合
	// s = "catsanddog",
	// dict = ["cat", "cats", "and", "sand", "dog"].
	//
	// A solution is ["cats and dog", "cat sand dog"].
	// 第一步：先用动态规划找出所有的断点，
	// 题目中的例子来说，在位置0，可以选择cats或者cat，下一断点为3和4。
	// buildPos()方法实现。
	// 第二步：使用递归列出所有解。我的代码中的printResult()方法实现。

	private void buildPos(String s, Set<String> dict) {
		// 建立list容器，存取起点对应的终点下标
		List<Integer> list = new ArrayList<Integer>();
		// 从右到左扫描
		for (int i = s.length() - 1; i >= 0; i--) {
			int len = list.size();

			// 从右到左
			for (int j = len - 1; j >= 0; j--) {
				// 获取list中的起点下标
				int index = list.get(j);
				String sub = s.substring(i, index);
				if (dict.contains(sub)) {
					// 建立list2容器，存取起点对应的终点下标
					List<Integer> list2 = posMap.get(i);

					if (list2 == null) {
						list2 = new ArrayList<Integer>();
						posMap.put(i, list2);
					}
					list2.add(index);
				}
			}
			// 判断从i点到字符串末端的子字符串是否存在字典中
			String sub = s.substring(i);
			if (dict.contains(sub)) {
				// 检验是否已经插入
				List<Integer> list2 = posMap.get(i);
				if (list2 == null) {
					list2 = new ArrayList<Integer>();
					posMap.put(i, list2);
				}
				// 将末端下标+1插入
				list2.add(s.length());
			}

			// 判断当前起点在dict中是否存在词，即存在终点
			List<Integer> list2 = posMap.get(i);
			if (list2 != null && !list2.isEmpty()) {
				list.add(i);
			}

		}
	}

	private void printResult(String s, int pos, StringBuffer sb) {
		if (pos == s.length()) { // 如果已经到末端，就可以添加字符串
			result.add(sb.toString().trim());
			return;
		}
		// 读取posMap中的终点位置
		List<Integer> list = posMap.get(pos);
		// 加入S不能由字典dict组成，返回空值
		if (list == null || list.isEmpty())
			return;
		for (Integer newPos : list) {
			sb.append(' ');
			sb.append(s.substring(pos, newPos));

			// 往下递归读取
			printResult(s, newPos, sb);

			int appendLen = newPos - pos;
			// 增加了空格，删除的长度就得加1
			appendLen += 1;
			// 删除之前添加的字符，从之前的pos起点位置继续遍历posMap存入的终点位置
			sb.delete(sb.length() - appendLen, sb.length());
		}
	}

	// 建立一个hashmap，把每个起点作为key，起点对应的终点作为value。
	private HashMap<Integer, List<Integer>> posMap = new HashMap<Integer, List<Integer>>();

	// 存取每种结果
	private ArrayList<String> result = new ArrayList<String>();

	public List<String> wordBreak2(String s, Set<String> dict) {
		posMap.clear();
		result.clear();
		if (s == null || dict == null || dict.isEmpty()) {
			return null;
		}
		buildPos(s, dict);

		StringBuffer sb = new StringBuffer();
		printResult(s, 0, sb);

		return result;
	}

	// 给定一个数字字符串，得到所有的编码总数，A-Z对应于1-26
	// 不能出现连00的，0不能打头的，不能出现类似于30/40的
	public int numDecodings(String s) {
		if (s == null)
			return 0;
		s = s.trim();
		if (s.trim().equals(""))
			return 0;
		int len = s.length();
		int[] num = new int[len];
		if (s.charAt(0) == '0')
			num[0] = 0;
		else
			num[0] = 1;
		for (int i = 1; i < len; i++) {
			if (s.charAt(i) == '0') {
				if (s.charAt(i - 1) == '0' || s.charAt(i - 1) >= '3')
					return 0;
				if (i == 1)
					num[i] = 1;
				else
					num[i] = num[i - 2];
			} else if (s.charAt(i - 1) == '1') {
				if (i == 1)
					num[i] = 2;
				else
					num[i] = num[i - 1] + num[i - 2];
			} else if (s.charAt(i - 1) == '2') {
				if (s.charAt(i) > '6') {
					num[i] = num[i - 1];
				} else {
					if (i == 1)
						num[i] = 2;
					else
						num[i] = num[i - 1] + num[i - 2];
				}
			} else {
				num[i] = num[i - 1];
			}
		}
		return num[len - 1];
	}

	// 找出数组中最大乘积的子数组
	public int maxProduct(List<Integer> nums) {
		if (nums.isEmpty())
			return 0;
		if (nums.size() == 1)
			return nums.get(0);
		int len = nums.size();
		int minTemp = nums.get(0);// 当前最小值
		int maxTemp = nums.get(0);// 当前最大值
		int maxProduct = nums.get(0);// 记录最大值
		int preMinTemp;// 前一个点的最小值
		for (int i = 1; i < len; i++) {
			preMinTemp = minTemp;
			// 当前最小值min( minTemp * nums.get(i), maxTemp * nums.get(i),
			// nums.get(i))
			minTemp = Math.min(
					Math.min(minTemp * nums.get(i), maxTemp * nums.get(i)),
					nums.get(i));
			// 当前最大值max(nums.get(i)*maxTemp , preMinTemp * nums.get(i) ,
			// nums.get(i))
			maxTemp = Math.max(
					Math.max(nums.get(i) * maxTemp, preMinTemp * nums.get(i)),
					nums.get(i));
			// 判断最大值
			maxProduct = Math.max(maxTemp, maxProduct);
		}
		return maxProduct;
	}

	// 找出数组中最大和的子数组
	public int maxSubArray(List<Integer> nums) {
		if (nums.size() == 1)
			return nums.get(0);
		int[] num = new int[nums.size()];
		int max = 0;
		int i = 0;
		for (Integer n : nums) {
			if (i == 0) {
				num[i] = n;
				max = n;
				i++;
				continue;
			}
			num[i] = Math.max(n, num[i - 1] + n);
			max = Math.max(max, num[i]);
			i++;
		}
		return max;
	}

	// 找出矩阵中最小和的路径
	public int minPathSum(int[][] grid) {
		int m = grid.length;
		if (m == 0)
			return 0;
		int n = grid[0].length;
		if (n == 0)
			return 0;
		// 第一列累计值
		for (int i = 1; i < m; i++) {
			grid[i][0] = grid[i - 1][0] + grid[i][0];
		}
		// 第一行累计值
		for (int j = 1; j < n; j++) {
			grid[0][j] = grid[0][j - 1] + grid[0][j];
		}
		// 迭代计算每个节点的累计值
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				grid[i][j] = grid[i][j]
						+ Math.min(grid[i - 1][j], grid[i][j - 1]);
			}
		}
		// 返回最小值
		return grid[m - 1][n - 1];
	}

	// 找出三角形中和最小的路径
	public int minimumTotal(List<List<Integer>> triangle) {
		int size = triangle.size();
		if (size == 0)
			return 0;
		int[] num = new int[size * (size + 1) / 2];// 存储每个节点的最小值
		int i = 0, j = 0;// i表示第几个，j表示第几层
		for (List<Integer> tri : triangle) {
			for (Integer t : tri) {
				if (j == 0) {// 第一层
					num[i] = t;
				} else if (j == 1) {// 第二层
					num[i] = t + num[0];
				} else if (i == j * (j + 1) / 2) {// 第三层以下，左侧
					num[i] = t + num[j * (j - 1) / 2];
				} else if (i == j * (j + 1) / 2 + j) {// 第三层以下，右侧
					num[i] = t + num[j * (j + 1) / 2 - 1];
				} else {// 第三层以下，中间元素，
					num[i] = t + Math.min(num[i - j], num[i - j - 1]);
				}
				i++;
			}
			j++;
		}
		// 遍历最底层，找出最小值
		int min = num[size * (size - 1) / 2];
		for (i = size * (size - 1) / 2; i < num.length; i++) {
			min = Math.min(min, num[i]);
		}
		return min;
	}

	// 加入引入障碍物，计算m*n矩阵中的全部路径数
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length;
		if (m == 0)
			return 0;
		int n = obstacleGrid[0].length;
		if (n == 0)
			return 0;
		int[][] dp = new int[m][n];
		// 计算第一列的值，遇障碍物后面全为0
		boolean flag = false;
		for (int i = 0; i < m; i++) {
			if (obstacleGrid[i][0] == 1) {
				flag = true;
				dp[i][0] = 0;
			}
			if (!flag)
				dp[i][0] = 1;
		}
		// 计算第一行的值，遇障碍物后面全为0
		flag = false;
		for (int j = 0; j < n; j++) {
			if (obstacleGrid[0][j] == 1) {
				flag = true;
				dp[0][j] = 0;
			}
			if (!flag)
				dp[0][j] = 1;
		}
		// 迭代，遇障碍物该点处置为0，继续累加
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if (obstacleGrid[i][j] == 1) {
					dp[i][j] = 0;
				} else {
					dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
				}
			}
		}
		return dp[m - 1][n - 1];
	}

	// 给定字典dict，将字符串S分割多个由字典里的字符组成
	public boolean wordBreak(String s, Set<String> wordDict) {
		if (s == null || wordDict == null) {
			return false;
		}
		int len = s.length();
		int left = 0;
		int right = 0;
		while (left < len && right <= len && left <= right) {
			String str = s.substring(left, right);
			if (wordDict.contains(str)) {
				left = right;
				if (left == len) {
					return true;
				}
			} else {
				right++;
			}
		}

		left = 0;
		right = len;
		while (left < len && left <= right) {
			String str = s.substring(left, right);
			if (wordDict.contains(str)) {
				right = left;
				left = 0;
				if (right == 0) {
					return true;
				}
			} else {
				left++;
			}
		}

		return false;
	}

	// m*n矩阵，从左上顶点到右下角的全部路径总数
	public int uniquePaths(int m, int n) {
		if (m < 1 || n < 1)
			return 0;
		if (m == 1 || n == 1)
			return 1;
		int[][] dp = new int[m][n];
		for (int i = 0; i < m; i++)
			dp[i][0] = 1;
		for (int j = 0; j < n; j++)
			dp[0][j] = 1;
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
		return dp[m - 1][n - 1];
	}

	// 爬楼梯，斐波那数列
	public int climbStairs(int n) {
		if (n < 0)
			return 0;
		if (n < 3)
			return n;
		int[] num = new int[n];
		num[0] = 1;
		num[1] = 2;
		for (int i = 2; i < n; i++) {
			num[i] = num[i - 1] + num[i - 2];
		}
		return num[n - 1];
	}

	// 不能同时偷相近的房屋，能偷的最多钱
	public int rob(int[] num) {
		if (num.length < 1)
			return 0;
		int len = num.length;
		// 维护两个数组，一个包含第一个，一个不包含第一个
		int[] hasFirst = new int[len];
		int[] noFirst = new int[len];
		hasFirst[0] = num[0];
		for (int i = 1; i < num.length; i++) {
			hasFirst[i] = noFirst[i - 1] + num[i];
			noFirst[i] = Math.max(hasFirst[i - 1], noFirst[i - 1]);
		}

		return Math.max(hasFirst[len - 1], noFirst[len - 1]);
	}

}
